常数|两端_20161230cppstlnote

篇首语：本文由编程笔记#小编为大家整理，主要介绍了20161230-cpp-stl-note相关的知识，希望对你有一定的参考价值。

引言

STL全程是Standard Template Library&＃xff0c;也就是这个库通过C&＃43;&＃43; Template的方式实现的标准库。这里面包括容器、迭代器、仿函数、常用的基本算法等。 几乎所有的代码都采用了模板类或者模板函数&＃xff0c;这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。本文主要对日常开发中常用的容器进行总结。

vector

vector 的数据安排以及操作方式&＃xff0c;与 array 非常相似。两者的唯一区别在于空间的运用的灵活性。array 是静态空间&＃xff0c;一旦配置了就不能改变&＃xff0c;vector 是动态数组。在堆上分配空间。vector 是动态空间&＃xff0c;随着元素的加入&＃xff0c;它的内部机制会自行扩充空间以容纳新元素&＃xff08;有保留内存&＃xff0c;如果减少大小后内存也不会释放。如果新值>当前大小时才会再分配内存&＃xff0c;这大大影响了 vector 的效率&＃xff09;。因此&＃xff0c;vector 的运用对于内存的合理利用与运用的灵活性有很大的帮助&＃xff0c;我们再也不必因为害怕空间不足而一开始要求一个大块的 array。

vector 动态增加大小&＃xff0c;并不是在原空间之后持续新空间&＃xff08;因为无法保证原空间之后尚有可供配置的空间&＃xff09;&＃xff0c;而是以原大小的两倍另外配置一块较大的空间&＃xff0c;然后将原内容拷贝过来&＃xff0c;然后才开始在原内容之后构造新元素&＃xff0c;并释放原空间。因此&＃xff0c;对 vector 的任何操作&＃xff0c;一旦引起空间重新配置&＃xff0c;同时指向原vector 的所有迭代器就都失效了。

对最后元素操作最快&＃xff08;在后面添加删除最快&＃xff09;&＃xff0c;此时一般不需要移动内存。对中间和开始处进行添加删除元素操作需要移动内存。如果你的元素是结构或是类,那么移动的同时还会进行构造和析构操作&＃xff0c;所以性能不高&＃xff08;最好将结构或类的指针放入 vector 中&＃xff0c;而不是结构或类本身&＃xff0c;这样可以避免移动时的构造与析构&＃xff09;。访问方面&＃xff0c;对任何元素的访问都是 O(1)&＃xff0c;也就是常数时间的。

总结&＃xff1a;

vector 常用来保存需要经常进行随机访问的内容&＃xff0c;并且不需要经常对中间元素进行添加删除操作。

STL源码剖析&＃xff1a;

https://blog.csdn.net/weixin_40673608/article/details/87103742

list

相对于 vector 的连续空间&＃xff0c;list 就显得复杂许多&＃xff0c;它的好处是每次插入或删除一个元素&＃xff0c;就配置或释放一个元素空间&＃xff0c;元素也是在堆中。因此&＃xff0c;list 对于空间的运用有绝对的精准&＃xff0c;一点也不浪费。而且&＃xff0c;对于任何位置的元素插入或元素移除&＃xff0c;永远是常数时间。STL 中的list 底层是一个双向链表&＃xff0c;而且是一个环状双向链表。这个特点使得它的随即存取变的非常没有效率&＃xff0c;因此它没有提供 [] 操作符的重载。

总结&＃xff1a;

如果你喜欢经常添加删除大对象的话&＃xff0c;那么请使用 list&＃xff1b;

要保存的对象不大&＃xff0c;构造与析构操作不复杂&＃xff0c;那么可以使用 vector 代替。

list<指针> 完全是性能最低的做法&＃xff0c;这种情况下还是使用 vector<指针> 好&＃xff0c;因为指针没有构造与析构&＃xff0c;也不占用很大内存

deque

deque 是一种双向开口的连续线性空间&＃xff0c;元素也是在堆中。所谓双向开口&＃xff0c;意思是可以在队尾两端分别做元素的插入和删除操作。deque 和 vector 的最大差异&＃xff0c;一在于 deque 允许于常数时间内对起头端进行元素的插入或移除操作&＃xff0c;二在于deque没有所谓容量观念&＃xff0c;因为它是动态地以分段连续空间组合而成&＃xff0c;随时可以增加一段新的空间并链接在一起。换句话说&＃xff0c;像 vector 那样“因旧空间不足而重新配置一块更大空间&＃xff0c;然后复制元素&＃xff0c;再释放旧空间”这样的事情在 deque 是不会发生的。它的保存形式如下:

[堆1] --> [堆2] -->[堆3] --> ...

deque 是由一段一段的定量连续空间构成。一旦有必要在 deque 的前端或尾端增加新空间&＃xff0c;便配置一段定量连续空间&＃xff0c;串接在整个 deque 的头端或尾端。deque 的最大任务&＃xff0c;便是在这些分段的定量连续空间上&＃xff0c;维护其整体连续的假象&＃xff0c;并提供随机存取的接口。避开了“重新配置&＃xff0c;复制&＃xff0c;释放”的轮回&＃xff0c;代价则是复杂的迭代器架构。因为有分段连续线性空间&＃xff0c;就必须有中央控制器&＃xff0c;而为了维持整体连续的假象&＃xff0c;数据结构的设计及迭代器前进后退等操作都颇为繁琐。

deque 采用一块所谓的 map 作为主控。这里的 map 是一小块连续空间&＃xff0c;其中每个元素都是指针&＃xff0c;指向另一段连续线性空间&＃xff0c;称为缓冲区。缓冲区才是 deque 的存储空间主体。&＃xff08; 底层数据结构为一个中央控制器和多个缓冲区&＃xff09;SGI STL 允许我们指定缓冲区大小&＃xff0c;默认值 0 表示将使用 512 bytes 缓冲区。

支持[]操作符&＃xff0c;也就是支持随即存取&＃xff0c;可以在前面快速地添加删除元素&＃xff0c;或是在后面快速地添加删除元素&＃xff0c;然后还可以有比较高的随机访问速度和vector 的效率相差无几。deque 支持在两端的操作&＃xff1a;push_back,push_front,pop_back,pop_front等&＃xff0c;并且在两端操作上与 list 的效率也差不多。

在标准库中 vector 和 deque 提供几乎相同的接口&＃xff0c;在结构上区别主要在于在组织内存上不一样&＃xff0c;deque 是按页或块来分配存储器的&＃xff0c;每页包含固定数目的元素&＃xff1b;相反 vector 分配一段连续的内存&＃xff0c;vector 只是在序列的尾段插入元素时才有效率&＃xff0c;而 deque 的分页组织方式即使在容器的前端也可以提供常数时间的 insert 和 erase 操作&＃xff0c;而且在体积增长方面也比 vector 更具有效率。

详细实现信息可以参考: http://c.biancheng.net/view/6908.html

如果deque中的map满了怎么办&＃xff1f;

总结&＃xff1a;

• vector 是可以快速地在最后添加删除元素&＃xff0c;并可以快速地访问任意元素&＃xff1b;
• list 是可以快速地在所有地方添加删除元素&＃xff0c;但是只能快速地访问最开始与最后的元素&＃xff1b;
• deque 在开始和最后添加元素都一样快&＃xff0c;并提供了随机访问方法&＃xff0c;像vector一样使用 [] 访问任意元素&＃xff0c;但是随机访问速度比不上vector快&＃xff0c;因为它要内部处理堆跳转。deque 也有保留空间。另外&＃xff0c;由于 deque 不要求连续空间&＃xff0c;所以可以保存的元素比 vector 更大。还有就是在前面和后面添加元素时都不需要移动其它块的元素&＃xff0c;所以性能也很高。

因此在实际使用时&＃xff0c;如何选择这三个容器中哪一个&＃xff0c;一般应遵循下面的原则&＃xff1a;

• 如果你需要高效的随即存取&＃xff0c;而不在乎插入和删除的效率&＃xff0c;使用 vector&＃xff1b;
• 如果你需要大量的插入和删除&＃xff0c;而不关心随即存取&＃xff0c;则应使用 list&＃xff1b;
• 如果你需要随即存取&＃xff0c;而且关心两端数据的插入和删除&＃xff0c;则应使用deque。

stack

stack 是一种先进后出&＃xff08;First In Last Out , FILO&＃xff09;的数据结构。它只有一个出口&＃xff0c;stack 允许新增元素&＃xff0c;移除元素&＃xff0c;取得最顶端元素。但除了最顶端外&＃xff0c;没有任何其它方法可以存取stack的其它元素&＃xff0c;stack不允许遍历行为。

以某种容器&＃xff08; 一般用 list 或 deque 实现&＃xff0c;封闭头部即可&＃xff0c;不用 vector 的原因应该是容量大小有限制&＃xff0c;扩容耗时&＃xff09;作为底部结构&＃xff0c;将其接口改变&＃xff0c;使之符合“先进后出”的特性&＃xff0c;形成一个 stack&＃xff0c;是很容易做到的。deque 是双向开口的数据结构&＃xff0c;若以 deque 为底部结构并封闭其头端开口&＃xff0c;便轻而易举地形成了一个stack。因此&＃xff0c;SGI STL 便以 deque 作为缺省情况下的 stack 底部结构&＃xff0c;由于 stack 系以底部容器完成其所有工作&＃xff0c;而具有这种“修改某物接口&＃xff0c;形成另一种风貌”之性质者&＃xff0c;称为 adapter&＃xff08;配接器&＃xff09;&＃xff0c;因此&＃xff0c;STL stack 往往不被归类为 container(容器)&＃xff0c;而被归类为 container adapter。

queue

queue 是一种先进先出&＃xff08;First In First Out,FIFO&＃xff09;的数据结构。它有两个出口&＃xff0c;queue 允许新增元素&＃xff0c;移除元素&＃xff0c;从最底端加入元素&＃xff0c;取得最顶端元素。但除了最底端可以加入&＃xff0c;最顶端可以取出外&＃xff0c;没有任何其它方法可以存取 queue 的其它元素。

以某种容器 &＃xff08; 一般用 list 或 deque 实现&＃xff0c;封闭头部即可 &＃xff0c;不用 vector 的原因应该是容量大小有限制&＃xff0c;扩容耗时 &＃xff09;作为底部结构&＃xff0c;将其接口改变&＃xff0c;使之符合“先进先出”的特性&＃xff0c;形成一个 queue&＃xff0c;是很容易做到的。deque 是双向开口的数据结构&＃xff0c;若以 deque 为底部结构并封闭其底部的出口和前端的入口&＃xff0c;便轻而易举地形成了一个 queue。因此&＃xff0c;SGI STL 便以 deque 作为缺省情况下的 queue 底部结构&＃xff0c;由于 queue 系以底部容器完成其所有工作&＃xff0c;而具有这种“修改某物接口&＃xff0c;形成另一种风貌”之性质者&＃xff0c;称为 adapter&＃xff08;配接器&＃xff09;&＃xff0c;因此&＃xff0c;STL queue 往往不被归类为container(容器)&＃xff0c;而被归类为 container adapter。

stack 和 queue 其实是适配器&＃xff0c;而不叫容器&＃xff0c;因为是对容器的再封装。

heap

heap 并不归属于 STL 容器组件&＃xff0c;它是个幕后英雄&＃xff0c;扮演 priority queue&＃xff08;优先队列&＃xff09;的助手。priority queue 允许用户以任何次序将任何元素推入容器中&＃xff0c;但取出时一定按从优先权最高的元素开始取。按照元素的排列方式&＃xff0c;heap 可分为 max-heap 和 min-heap 两种&＃xff0c;前者每个节点的键值(key)都大于或等于其子节点键值&＃xff0c;后者的每个节点键值(key)都小于或等于其子节点键值。因此&＃xff0c; max-heap 的最大值在根节点&＃xff0c;并总是位于底层array或vector的起头处&＃xff1b;min-heap 的最小值在根节点&＃xff0c;亦总是位于底层array或vector起头处。STL 供应的是 max-heap&＃xff0c;用 C&＃43;&＃43; 实现。

priority_queue

priority_queue 是一个拥有权值观念的 queue&＃xff0c;它允许加入新元素&＃xff0c;移除旧元素&＃xff0c;审视元素值等功能。由于这是一个 queue&＃xff0c;所以只允许在底端加入元素&＃xff0c;并从顶端取出元素&＃xff0c;除此之外别无其它存取元素的途径。priority_queue 带有权值观念&＃xff0c;其内的元素并非依照被推入的次序排列&＃xff0c;而是自动依照元素的权值排列&＃xff08;通常权值以实值表示&＃xff09;。权值最高者&＃xff0c;排在最前面。缺省情况下 priority_queue 系利用一个 max-heap 完成&＃xff0c;后者是一个以vector 表现的 complete binary tree.max-heap 可以满足 priority_queue 所需要的“依权值高低自动递减排序”的特性。

priority_queue 完全以底部容器&＃xff08;一般为vector为底层容器&＃xff09;作为根据&＃xff0c;再加上 heap 处理规则&＃xff0c;所以其实现非常简单。缺省情况下是以 vector 为底部容器。queue 以底部容器完成其所有工作。具有这种“修改某物接口&＃xff0c;形成另一种风貌“”之性质者&＃xff0c;称为 adapter(配接器)&＃xff0c;因此&＃xff0c;STL priority_queue 往往不被归类为 container(容器)&＃xff0c;而被归类为 container adapter。

set 和 multiset 容器

set 的特性是&＃xff0c;所有元素都会根据元素的键值自动被排序。set 的元素不像 map 那样可以同时拥有实值(value)和键值(key)&＃xff0c;set 元素的键值就是实值&＃xff0c;实值就是键值&＃xff0c;set不允许两个元素有相同的值。set 底层是通过红黑树&＃xff08;RB-tree&＃xff09;来实现的&＃xff0c;由于红黑树是一种平衡二叉搜索树&＃xff0c;自动排序的效果很不错&＃xff0c;所以标准的 STL 的 set 即以 RB-Tree 为底层机制。又由于 set 所开放的各种操作接口&＃xff0c;RB-tree 也都提供了&＃xff0c;所以几乎所有的 set 操作行为&＃xff0c;都只有转调用 RB-tree 的操作行为而已。

multiset的特性以及用法和 set 完全相同&＃xff0c;唯一的差别在于它允许键值重复&＃xff0c;因此它的插入操作采用的是底层机制是 RB-tree 的 insert_equal() 而非 insert_unique()。

map 和 multimap 容器

map的特性是&＃xff0c;所有元素都会根据元素的键值自动被排序。map 的所有元素都是 pair&＃xff0c;同时拥有实值&＃xff08;value&＃xff09;和键值&＃xff08;key&＃xff09;。pair 的第一元素被视为键值&＃xff0c;第二元素被视为实值。map不允许两个元素拥有相同的键值。由于 RB-tree 是一种平衡二叉搜索树&＃xff0c;自动排序的效果很不错&＃xff0c;所以标准的STL map 即以 RB-tree 为底层机制。又由于 map 所开放的各种操作接口&＃xff0c;RB-tree 也都提供了&＃xff0c;所以几乎所有的 map 操作行为&＃xff0c;都只是转调 RB-tree 的操作行为。

multimap 的特性以及用法与 map 完全相同&＃xff0c;唯一的差别在于它允许键值重复&＃xff0c;因此它的插入操作采用的是底层机制 RB-tree 的 insert_equal() 而非 insert_unique。

unordered_set、unordered_map

hashtable作为unordered_set和unordered_map的底层数据结构&＃xff0c;是隐藏起来的&＃xff0c;正常不会直接用到它&＃xff0c;但要理解好unordered_set和unordered_map&＃xff0c;需要先理解好hashtable

hashtable的底层数据结构是vector&＃xff0c;vector中的元素是链表

vector代表篮子&＃xff0c;初始化大小为53&＃xff08;GNU的做法&＃xff09;&＃xff0c;存的是结点指针

元素放进来的时候&＃xff0c;会经过一个hash函数&＃xff0c;找到对应的篮子&＃xff0c;然后连在篮子的后面

当放进去的元素的数量超过vector的长度的时候&＃xff0c;就会执行rehashing&＃xff1a;

vector的大小会先变大为2倍&＃xff0c;但不一定是2倍&＃xff0c;会变成2倍左右的一个素数

vector变大后&＃xff0c;原先的每一个元素都需要重新用hash函数计算并放到对应的篮子里

如果还需要rehashing的话&＃xff0c;vector的大小会按照以下增长&＃xff0c;这些数字是已经先算好的&＃xff0c;vector在扩充的时候&＃xff0c;不会再花时间去计算&＃xff0c;而是直接在下面抓取对应的大小